#include<string>
#include<iostream>
#include<algorithm>
using std::min;
using std::string;


class Solution {
public:
    int minDistance(string word1, string word2) {
        if (word1.size() == 0) return word2.size();
        if (word2.size() == 0) return word1.size();

        int dp[word1.size()+1][word2.size()+1];
        for (int i = 1; i <= word1.size(); i++) {
            dp[i][0] = i; // word1 -> "" 需要的编辑距离
        }
        for (int j = 0; j <= word2.size(); j++) {
            dp[0][j] = j;
        }
        int d = 0;
        // DP
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                d = 1 * (word1[i-1] != word2[j-1]);
                dp[i][j] = min(dp[i-1][j-1] + d, min(dp[i][j-1] + 1, dp[i-1][j] + 1));
            }
        }
        // for (int i = 0; i <= word1.size(); i++) {
        //     for (int j = 0; j <= word2.size(); j++) {
        //         std::cout << dp[i][j] << " ";
        //     }
        //     std::cout << "\n";
        // }
        return dp[word1.size()][word2.size()];
    }
};


int main() {
    string word1, word2;
    std::getline(std::cin, word1);
    std::getline(std::cin, word2);
    std::cout << "Edit Distance: " << Solution().minDistance(word1, word2) << "\n";
    return 0;
}